{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "823da1c3",
   "metadata": {},
   "source": [
    "[141. 环形链表 - 力扣（LeetCode）](https://leetcode.cn/problems/linked-list-cycle/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "24ca4de4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 使用节点对象作为key，构建字典（hashMap）\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        hashMap = dict()\n",
    "        read = head\n",
    "        while read:\n",
    "            if read in hashMap:\n",
    "                return True\n",
    "            else:\n",
    "                read[read]=1\n",
    "            read = read.next\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6f6bde0",
   "metadata": {},
   "source": [
    "[142. 环形链表 II - 力扣（LeetCode）](https://leetcode.cn/problems/linked-list-cycle-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bea2eea3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 利用节点对象为key，序号为value，构建字典（hashMap）\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        hashMap = dict()\n",
    "        read = head\n",
    "        flag = False\n",
    "        while read:\n",
    "            if read in hashMap:\n",
    "                flag = True\n",
    "                break\n",
    "            else:\n",
    "                hashMap[read] = 1\n",
    "            read = read.next\n",
    "\n",
    "        if flag:\n",
    "            return read\n",
    "        else:\n",
    "            None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f48142c2",
   "metadata": {},
   "source": [
    "[143. 重排链表 - 力扣（LeetCode）](https://leetcode.cn/problems/reorder-list/submissions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1ea02d60",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 把节点读到list里面，左右指针，交替添加节点，左指针<=n//2+1\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        Lst = []\n",
    "        read = head.next\n",
    "        while read:\n",
    "            Lst.append(read)\n",
    "            read = read.next\n",
    "        n = len(Lst)\n",
    "\n",
    "        read = head\n",
    "        left,right = 0,n-1\n",
    "        while left<right:\n",
    "            read.next = Lst[right]\n",
    "            read = read.next\n",
    "            read.next = Lst[left]\n",
    "            left+=1\n",
    "            right-=1\n",
    "            read = read.next\n",
    "        if left==right: # 此时差一个左节点没有添加\n",
    "            read.next = Lst[left]\n",
    "            read = read.next\n",
    "        read.next = None # 最后一个节点指向None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b09c8dc9",
   "metadata": {},
   "source": [
    "[144. 二叉树的前序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-preorder-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d966e3d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 二叉树的前序遍历\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        \n",
    "        def preOrder(root:TreeNode)->None:\n",
    "            nonlocal res\n",
    "            if root:\n",
    "                res.append(root.val)\n",
    "                preOrder(root.left)\n",
    "                preOrder(root.right)\n",
    "        \n",
    "        preOrder(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03d660b0",
   "metadata": {},
   "source": [
    "[145. 二叉树的后序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-postorder-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0eddec3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "\n",
    "        def postOrder(root:TreeNode)->None:\n",
    "            if root:\n",
    "                postOrder(root.left)\n",
    "                postOrder(root.right)\n",
    "                res.append(root.val)\n",
    "\n",
    "        postOrder(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fad3a07",
   "metadata": {},
   "source": [
    "[146. LRU 缓存 - 力扣（LeetCode）](https://leetcode.cn/problems/lru-cache/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "95bb7b31",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__(self,key=None,val=None,prev=None,next=None):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "\n",
    "## LRUCache 使用hashMap实现O（1）查询， 在python中使用dict实现\n",
    "## 使用一个双向链表实现左侧插入，右侧移除过期值，\n",
    "## dict中存储的val是链表节点\n",
    "class LRUCache:\n",
    "    def __init__(self, capacity: int):\n",
    "        self.capacity = capacity\n",
    "        head = ListNode()\n",
    "        tail = ListNode()\n",
    "        head.next = tail\n",
    "        tail.prev = head\n",
    "        self.head = head\n",
    "        self.tail = tail\n",
    "        self.cache = dict()   # hashMap\n",
    "\n",
    "    def get(self, key: int) -> int:\n",
    "        # 不存在，返回-1\n",
    "        if key not in self.cache:\n",
    "            return -1\n",
    "        # 存在， 提到队首,返回队首值\n",
    "        else:\n",
    "            node = self.cache[key]\n",
    "            self.move2head(node)\n",
    "            return node.val\n",
    "    \n",
    "    \n",
    "    def put(self, key: int, value: int) -> None:\n",
    "        # 不存在，加入hashmap, 加入左侧链表首\n",
    "        if key not in self.cache:            \n",
    "            newN = ListNode(val=value,key=key)\n",
    "            self.cache[key] = newN\n",
    "            self.add2head(newN)\n",
    "            # 如果容量已满,删除最后一个结点\n",
    "            if len(self.cache)>self.capacity:\n",
    "                lastNode = self.tail.prev\n",
    "                self.rmNode(lastNode)\n",
    "                self.cache.pop(lastNode.key)\n",
    "        else: # 已经存在：更改对应的值\n",
    "            node = self.cache[key]\n",
    "            node.val = value\n",
    "            self.move2head(node)\n",
    "\n",
    "    def add2head(self, node):\n",
    "        node.next = self.head.next\n",
    "        node.prev = self.head\n",
    "        self.head.next.prev = node\n",
    "        self.head.next = node\n",
    "        \n",
    "    \n",
    "    def move2head(self, node):\n",
    "        # 已经在队首\n",
    "        if node == self.head.next:\n",
    "            return\n",
    "        # # 否则把结点先删除， 然后添加到队首\n",
    "        self.rmNode(node)\n",
    "        self.add2head(node)\n",
    "    \n",
    "    def rmNode(self, node):\n",
    "        node.next.prev = node.prev\n",
    "        node.prev.next = node.next\n",
    "\n",
    "    \n",
    "# Your LRUCache object will be instantiated and called as such:\n",
    "# obj = LRUCache(capacity)\n",
    "# param_1 = obj.get(key)\n",
    "# obj.put(key,value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28130e5f",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "351e07fc",
   "metadata": {},
   "source": [
    "[147. 对链表进行插入排序 - 力扣（LeetCode）](https://leetcode.cn/problems/insertion-sort-list/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91e8da13",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 使用数组进行插入排序\n",
    "# 1. 插入排序需要后向寻找，对于链表来说复杂度过高，因此使用数组\n",
    "# 2. 把数组排序完成后，恢复为链表\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        Lst = []\n",
    "        reader = head\n",
    "        i = 0\n",
    "        while reader:\n",
    "            if i==0:\n",
    "                Lst.append(reader)\n",
    "                i += 1\n",
    "                continue\n",
    "            j = i-1\n",
    "            ## 把新结点插入到合适的位置\n",
    "            Lst.append(reader) # 占据空位\n",
    "            while reader.val < Lst[j].val and j>=0:\n",
    "                Lst[j+1] = Lst[j] # 插入位置左移\n",
    "                j -= 1\n",
    "            Lst[j+1] = reader\n",
    "            ## 加载下一个结点\n",
    "            reader = reader.next\n",
    "            i += 1\n",
    "        \n",
    "        ## 把数组新建为链表\n",
    "        head2 = ListNode()\n",
    "        reader = head2\n",
    "        for node in Lst:\n",
    "            reader.next = node\n",
    "            reader = reader.next\n",
    "        reader.next = None\n",
    "\n",
    "        return head2.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b61a3c6",
   "metadata": {},
   "source": [
    "[148. 排序链表 - 力扣（Leetcode）](https://leetcode.cn/problems/sort-list/description/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a2fdd1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 两个难点\n",
    "# 1. 时间复杂度O(nlog(n))\n",
    "# 2. 空间复杂度O(1)\n",
    "# \n",
    "# 升序排列链表\n",
    "# 读到链表中，O(nlog(n)),归并or快排\n",
    "## 归并排序方案\n",
    "# 1.快慢指针，找到中间结点，以中间结点作为分割点，分为两个链表\n",
    "# 2. merge 函数把两个链表按顺序合并成一个链表，并返回\n",
    "\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or (not head.next):\n",
    "            return head\n",
    "\n",
    "        def merge(head1:ListNode,head2:ListNode)->ListNode:\n",
    "            reader = dummyhead = ListNode(val=None)\n",
    "            while head1 and head2:\n",
    "                if head1.val<head2.val:\n",
    "                    reader.next = head1\n",
    "                    reader = reader.next\n",
    "                    head1 = head1.next\n",
    "                else:\n",
    "                    reader.next = head2\n",
    "                    reader = reader.next\n",
    "                    head2 = head2.next\n",
    "            if head1:\n",
    "                reader.next = head1\n",
    "            if head2:\n",
    "                reader.next = head2\n",
    "            return dummyhead.next\n",
    "\n",
    "        fast,slower = head.next,head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slower = slower.next\n",
    "        mid = slower.next\n",
    "        slower.next = None # 分割链表\n",
    "\n",
    "        head1 = self.sortList(head)\n",
    "        head2 = self.sortList(mid)\n",
    "        return merge(head1,head2)\n",
    "\n",
    "\n",
    "def printNode(head):\n",
    "    Lst = []\n",
    "    while head:\n",
    "        Lst.append(head.val)\n",
    "        head =head.next\n",
    "    return Lst\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [4,2,1,3]#[1,5,3,4,8,2]\n",
    "    head = ListNode()\n",
    "    reader = head\n",
    "    for num in nums:\n",
    "        node = ListNode(val=num)\n",
    "        reader.next = node\n",
    "        reader = reader.next\n",
    "    solv = Solution()\n",
    "    newhead = solv.sortList(head.next)\n",
    "    # print head\n",
    "    print(printNode(newhead))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9edc9390",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 两个难点\n",
    "# 1. 时间复杂度O(nlog(n))\n",
    "# 2. 空间复杂度O(1)\n",
    "# \n",
    "# 升序排列链表\n",
    "# 读到链表中，O(nlog(n)),归并or快排\n",
    "## 快排方案\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if (not head) or (not head.next):\n",
    "            return head\n",
    "        ## 找到前导结点，后尾部结点\n",
    "        # 把链表分为3段，然后合并\n",
    "\n",
    "        def partation(head):\n",
    "            # 把尾部结点从链表中分离\n",
    "            pretail,tail = head,head.next\n",
    "            while tail and tail.next:\n",
    "                pretail = pretail.next\n",
    "                tail = tail.next\n",
    "            if tail:\n",
    "                pretail.next=None\n",
    "            else:  # 注意\n",
    "                return head\n",
    "            \n",
    "            reader = head\n",
    "            h1 = head1 = ListNode(None)\n",
    "            h2 = head2 = ListNode(None)\n",
    "            h3 = head3 = ListNode(None)\n",
    "            while reader:\n",
    "                if reader.val < tail.val:\n",
    "                    h1.next = reader\n",
    "                    h1 = h1.next\n",
    "                else:\n",
    "                    h3.next = reader\n",
    "                    h3 = h3.next\n",
    "                reader = reader.next\n",
    "            h2.next = tail\n",
    "            h1.next = None\n",
    "            h3.next = None\n",
    "\n",
    "            return head1.next,head2.next,head3.next\n",
    "\n",
    "        \n",
    "        def cat(left,mid,right):\n",
    "            reader = dummyHead = ListNode(val=None)\n",
    "            while left:\n",
    "                reader.next = left\n",
    "                reader = reader.next\n",
    "                left = left.next\n",
    "            while mid:\n",
    "                reader.next = mid\n",
    "                reader = reader.next\n",
    "                mid = mid.next\n",
    "            while right:\n",
    "                reader.next = right\n",
    "                reader = reader.next\n",
    "                right = right.next\n",
    "            reader.next = None\n",
    "            return dummyHead.next\n",
    "\n",
    "        head1,head2,head3 = partation(head)\n",
    "        left  = self.sortList(head1)\n",
    "        right = self.sortList(head3)\n",
    "        return cat(left,head2,right)\n",
    "\n",
    "def printNode(head):\n",
    "    Lst = []\n",
    "    while head:\n",
    "        Lst.append(head.val)\n",
    "        head =head.next\n",
    "    return Lst\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [4,2,1,3]#[1,5,3,4,8,2]\n",
    "    head = ListNode()\n",
    "    reader = head\n",
    "    for num in nums:\n",
    "        node = ListNode(val=num)\n",
    "        reader.next = node\n",
    "        reader = reader.next\n",
    "    solv = Solution()\n",
    "    newhead = solv.sortList(head.next)\n",
    "    # print head\n",
    "    print(printNode(newhead))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a32d53c7",
   "metadata": {},
   "source": [
    "[149. 直线上最多的点数 - 力扣（Leetcode）](https://leetcode.cn/problems/max-points-on-a-line/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c6ae9dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 先确定平行线上的点，在计算便宜\n",
    "# 使用hashmap\n",
    "# 难点在于由于精度问题，key不能准确的表示\n",
    "# 因此我们使用分数dy/dx的字符串形式表示斜率\n",
    "# 为了斜率的分数应该是化到最简后的形式，分子分母同时除最大公约数\n",
    "# 斜率的正负问题：为了统一，我们把符号位统一放在分母上\n",
    "# 已知斜率和线上的一个点，可以唯一的确定一个直线\n",
    "# 使用gcd（最大公约数）\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxPoints(self, points: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        from math import gcd\n",
    "\n",
    "        n = len(points)\n",
    "        maxNums = 1\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            lines = defaultdict(set)\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                x2, y2 = points[j]\n",
    "                if x2-x1 == 0:\n",
    "                    a = '0'\n",
    "                else:\n",
    "                    k = gcd(y2-y1, x2-x1)\n",
    "                    dy, dx = y2-y1, x2-x1\n",
    "                    if dx < 0:\n",
    "                        dy, dx = -dy, -dx\n",
    "                    a = '{}-{}'.format(dy/k, dx/k)\n",
    "                # b = y1-a*x1\n",
    "                lines[a].add((x1, y1))\n",
    "                lines[a].add((x2, y2))\n",
    "\n",
    "            for key in lines:\n",
    "                maxNums = max(maxNums, len(lines[key]))\n",
    "\n",
    "        return maxNums"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a396ca81",
   "metadata": {},
   "source": [
    "[150. 逆波兰表达式求值 - 力扣（Leetcode）](https://leetcode.cn/problems/evaluate-reverse-polish-notation/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b5437fa5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 逆波兰表达式\n",
    "# 栈操作\n",
    "## 注意在除法操作的时候，(1//-5)=-1, //: 表示向下取整\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        from math import floor\n",
    "        Lst = []\n",
    "        ens = set(['*', '/', '+', '-'])\n",
    "        for s in tokens:\n",
    "            if s not in ens:\n",
    "                Lst.append(int(s))\n",
    "            else:\n",
    "                x2 = Lst.pop(-1)\n",
    "                x1 = Lst.pop(-1)\n",
    "                if s == '*':\n",
    "                    res = x1*x2\n",
    "                elif s == '/':\n",
    "                    res = int(x1/x2)\n",
    "                elif s == '+':\n",
    "                    res = x1+x2\n",
    "                elif s == '-':\n",
    "                    res = x1-x2\n",
    "                Lst.append(res)\n",
    "        return Lst.pop(-1)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    token = [\"10\", \"6\", \"9\", \"3\", \"+\", \"-11\",\n",
    "             \"*\", \"/\", \"*\", \"17\", \"+\", \"5\", \"+\"]\n",
    "    solv = Solution()\n",
    "    print(solv.evalRPN(token))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
